Komplexitätstheorie

Komplexitätstheorie,

 

Forschungsgebiet der Mathematik, in dem man sich mit dem Rechenaufwand (der Komplexität) von Algorithmen beschäftigt. Hauptziel ist es, zu einem Problem den Algorithmus mit dem geringsten Rechenaufwand zu ermitteln. Die Komplexitätstheorie ist damit insbesondere für die Informatik von Bedeutung, da Computer prinzipiell nur zur Lösung solcher Probleme anwendbar sind, für die Algorithmen existieren. Die Komplexität, d. h. in Bezug auf Computer v. a. die Rechenzeit und der Bedarf an Speicherplatz, einiger Algorithmen ist jedoch sehr hoch; im Wesentlichen sind nur Algorithmen geeignet, deren Rechenaufwand sich durch ein Polynom abschätzen lässt (polynomiale Komplexität). Die Komplexitätstheorie konnte zeigen, dass für einige Probleme zwar Algorithmen existieren, aber keine mit polynomialer Komplexität.

 

Literatur:

 

J. E. Hopcroft u. J. D. Ullman: Einf. in die Automatentheorie, formale Sprachen u. K. (a. d. Amerikan., ³1994).